import java.math.BigDecimal;
import java.math.RoundingMode;

/**
 * <p>简单背包问题</p>
 *
 * @author: YuanChilde
 * @date: 2020-02-18 13:35
 * @version: 1.0
 * Modification History:
 * Date    Author      Version     Description
 * -----------------------------------------------------------------
 * 2020-02-18 13:35    YuanChilde     1.0        新增
 */
public class KnapsackProblem {
    public static void main(String[] args){

        float knapsackWeight = 4;
        float[] itemsWeights = new float[] {1, 4, 3};
        float[] itemsPrices = new float[] {1500, 3000, 2000};
        float[][] table = knapsackSolution(knapsackWeight, itemsWeights, itemsPrices);

        for (int line = 0; line < table.length; line++ ) {
            System.out.println("-----------------line =" + line);
            for (int colume = 0; colume < table[line].length; colume++ ) {
                System.out.println(table[line][colume] + ",");
            }
        }
    }

    /**
     *
     * @param knapsackWeight 背包总容量
     * @param itemsWeights    各个物品的所占据的容量
     * @param itemsPrices     各个物品所具有的价值
     * @return
     */
    public static float[][] knapsackSolution(float knapsackWeight, float[] itemsWeights, float[] itemsPrices) {
        if (itemsWeights.length != itemsPrices.length) {
            throw new IllegalArgumentException();
        }

        //计算表格的行数 --物品数量
        int lines = itemsPrices.length;
        //计算出划分的背包最小的空间，即表格每一列代表的重量为  column * minWeight
        float minWeight = getMinWeight(itemsWeights);
        //计算表格的列数 --分割出的重量数目
        int colums = (int) (knapsackWeight/minWeight);
        System.out.println("lines = " + lines + ",colums = " + colums + ",minWeight = " + minWeight);
        //创建表格对象,lines行colums列
        float[][] table = new float[lines][colums];

        for (int line = 0; line < lines; line++ ) {
            for (int colume = 0; colume < colums; colume++ ) {

                float left = table[(line - 1) < 0 ? 0 : (line - 1) ][colume];
                float right = 0;
                //判断当前划分的小背包是否可以装下该物品，当前背包容量为(colume +1)*minWeight
                if ((colume +1)*minWeight >= itemsWeights[line]) {
                    //获取当前背包剩余空间
                    float freeWeight = ((colume+1)*minWeight - itemsWeights[line]);
                    //判断剩余空间是否还可以装下其它的东西
                    int freeColumn = (int) (freeWeight/minWeight) - 1;
                    if (freeColumn >= 0 && line > 0) {
                        //因为表格上同一列的位置上，越往下价值越高，所以这边直接取的上一行的freeColumn位置就行
                        right = itemsPrices[line] + table[line - 1][freeColumn];
                    }else {
                        right = itemsPrices[line];
                    }
                }

                table[line][colume] = Math.max(left, right);
            }

        }
        return table;

    }

    /**
     * 获取所有物品中最小的重量
     *
     * @param itemsWeights 各个物品的所占据的容量
     * @return
     */
    public static float getMinWeight(float[] itemsWeights) {
        float min = itemsWeights[0];

        for (float weight : itemsWeights) {
            min = min > weight ? weight : min;
        }
        //保留最多2位小数，并默认非零就进位1.222 --> 1.23
        //为啥String.valueOf，参照https://www.cnblogs.com/LeoBoy/p/6056394.html
        return new BigDecimal(String.valueOf(min)).setScale(2, RoundingMode.UP).floatValue();
    }
}
